int strStr(char *haystack, char *needle)
{
    int n = strlen(haystack), m = strlen(needle);
    if (m == 0)
        return 0;
    int pi[m];
    pi[0] = 0;

    for (int i = 1, j = 0; i < m; i++)
    {
        // j is the suffix str's next word, if needle[i] == needle[j], the suffix's len++
        // else try to compare the suffix of 0~j-1's next(needle[j]) word and needle[i]
        while (j > 0 && needle[i] != needle[j])
            j = pi[j - 1];
        //可以保证的是前缀匹配子串的和新增的i前面的后缀串相同的，如果能保证i和j位置的值相等，那么就比找到的这个前缀子串长度多一
        if (needle[i] == needle[j])
            j++;
        pi[i] = j;
    }

    for (int i = 0, j = 0; i < n; i++)
    {
        //当i不断增加时，如果能够匹配，那么i迟早会是pi[m-1]的前缀字符串的最后一位，如果继续增加到最后，就得到了匹配的字符串根据偏移能找到位置
        //如果不能找到匹配的字符串，尝试匹配下一级的前缀字符串，以减少下次的匹配数量
        while (j > 0 && haystack[i] != needle[j])
            j = pi[j - 1];
        if (haystack[i] == needle[j])
            j++;
        if (j == m)
            return i - m + 1;
    }
    return -1;
}